package niuke;
import java.util.*;
//class TreeNode {
//    int val = 0;
//    TreeNode left = null;
//    TreeNode right = null;
//
//    public TreeNode(int val) {
//        this.val = val;
//    }
//}
////class Node {
//    int val;
//    Node next;
//    Node random;
//
//    public Node(int val) {
//        this.val = val;
//        this.next = null;
//        this.random = null;
//    }
//}
//public class niuKeMain1 {
//    public void remove(int key) {
//        TreeNode cur = root;
//        TreeNode parent = null;
//        while (cur != null) {
//            if(cur.val < key) {
//                parent = cur;
//                cur = cur.right;
//            }else if(cur.val == key) {
//                removeNode(parent,cur);
//                return;
//            }else {
//                parent = cur;
//                cur = cur.left;
//            }
//        }
//    }
//    public void removeNode(TreeNode parent,TreeNode cur) {
//        if(cur.left == null) {
//            if(cur == root) {
//                root = cur.right;
//            }else if(cur == parent.left) {
//                parent.left = cur.right;
//            }else {
//                parent.right = cur.right;
//            }
//        }else if(cur.right == null) {
//            if(cur == root) {
//                root = cur.left;
//            }else if(cur == parent.left) {
//                parent.left = cur.left;
//            }else {
//                parent.right = cur.left;
//            }
//        }else {
//            TreeNode node = cur.right;
//            TreeNode prev = null;
//            while (node.left != null) {
//                prev=node;
//                node = node.left;
//            }
//            cur.val=node.val;
//            if (prev.left==cur){
//                prev.left=cur.right;
//            }
//            else if(prev.right==cur){
//                prev.right=cur.right;
//            }
//        }
//    }
//
//public Node copyRandomList(Node head) {
//    if (head==null){
//        return null;
//    }
//    Node cur=head;
//    Map<Node,Node> map=new HashMap<>();
//    while (cur!=null){
//        map.put(cur,new Node(cur.val));
//        cur=cur.next;
//    }
//    cur=head;
//    while (cur!=null){
//        map.get(cur).next=map.get(cur.next);
//        map.get(cur).random=map.get(cur.random);
//        cur=cur.next;
//    }
//    return map.get(head);
//}
//public int numJewelsInStones(String jewels, String stones) {
//    HashSet<Character> set=new HashSet<>();
//    for (int i=0;i<jewels.length();i++){
//        set.add(jewels.charAt(i));
//    }
//    int count=0;
//    for (int i=0;i<stones.length();i++){
//        if (set.contains(stones.charAt(i))){
//            count++;
//        }
//    }
//    return count;
//}
//public static void main(String[] args) {
//    int[] array = new int[10];
//    Random random = new Random();
//    for (int i = 0; i < array.length; i++) {
//        array[i] = random.nextInt(5);
//    }
//
//    HashMap<Integer,Integer> map = new HashMap<>();
//
////判断数组的数据 是否在map中 没有就是1 1   有 1   value+1
//    for (int i = 0; i < array.length; i++) {
//        if (map.containsKey(array[i])){
//            int value=map.get(array[i]);
//            map.put(array[i],value+1);
//        }
//        else {
//            map.put(array[i],1);
//        }
//    }
//    for (Map.Entry<Integer,Integer> maps:map.entrySet()) {
//        System.out.println("key:"+maps.getKey()+"value:"+maps.getValue());
//    }
////
//}
//        public boolean isPail (ListNode head) {
//            if (head==null){
//                return true;
//            }
//            ListNode slow=head;
//            ListNode fast=head;
//            while (fast!=null&&fast.next!=null){
//                fast=fast.next.next;
//                slow=slow.next;
//            }
//            ListNode n1=slow;
//            ListNode n2=slow.next;
//            while (n2!=null){
//                n1=n2;
//                n2=n2.next;
//                n1.next=slow;
//                slow=n1;
//            }
//            ListNode n3=head;
//            while(n3!=slow&&n3.next!=slow){
//                if(n3.val!=slow.val){
//                    return false;
//                }
//                n3=n3.next;
//                slow=slow.next;
//            }
//            return true;
//        }
//        public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
//            ArrayList<ArrayList<Integer>> list=new ArrayList<>();
//            if (pRoot==null){
//                return list;
//            }
//            TreeNode root=pRoot;
//            Queue<TreeNode> queue=new LinkedList<>();
//            queue.offer(root);
//            while (!queue.isEmpty()){
//                    int size= queue.size();
//                    ArrayList<Integer> list1=new ArrayList<>();
//                    while (size>0){
//                        root=queue.poll();
//                        list1.add(root.val);
//                        if (root.left!=null){
//                            queue.offer(root.left);
//                        }
//                        if(root.right!=null){
//                            queue.offer(root.right);
//                        }
//                        size--;
//                }
//                list.add(list1);
//            }
//            return list;
//        }
//
//    public static void main2(String[] args) {
//        Set<Integer> set=new HashSet<>();
//        int[] arr=new int[100000];
//        Random random=new Random();
//        for (int i = 0; i < arr.length; i++) {
//            arr[i]=random.nextInt(1_000);
//        }
//        for (int i = 0; i < arr.length; i++) {
//                set.add(arr[i]);
//        }
//    }
//    public static void main1(String[] args) {
//        Set<Integer> set=new HashSet<>();
//        int[] arr=new int[100000];
//        Random random=new Random();
//        for (int i = 0; i < arr.length; i++) {
//            arr[i]=random.nextInt(1_000);
//        }
//        for (int i = 0; i < arr.length; i++) {
//            if (set.contains(arr[i])){
//                System.out.println(arr[i]);
//            }
//            else {
//                set.add(arr[i]);
//            }
//        }
//    }
//}
//
